# include "alloc.h"

static Graph *allocGraph;
static ArrayList *allocNodes;
static ArrayList *mapUCEs;
static ArrayList *notAlloced;

static int getIndice (char *uce);
static int getIndiceLst (char *uce, LinkedList *ops);
static int canAdd (char *uceA, char *uceB);
static int canAddA (char *uce);
static int compSelections (void *a,void *b);
static void assignStudent (Student *st, int a, int b, int c);
static void insereAluno (Student *st, char *u);
static int temAluno (Student *st, int i);
static void distribui ();

static int temAluno (Student *st, int uce) {
	ArrayList *lst = arrayGet(allocNodes,uce);
	int n = arrayGetLength(lst);
	int i; Student *aux;
	for (i=0;i<n;i++) {
		aux = arrayGet(lst,i);
		if (aux->number == st->number) return 1;
	}
	return 0;
}

static int studentCompareA (void *a, void *b) {
	Student *stA = a;
	Student *stB = b;
	return compareStudent(stA,stB);
}

static void assignStudentA (Student *st, char *uce, int d) {
	int iA = getIndiceLst(uce,st->selections);
	int n = listSize(st->selections);
	int i;
	Selection *sel;
	int add = 0;
	LinkedList *l = st->selections;
	if (st->ucesWanted > 2) {
		for (i=0;i<n;i++) if (i!=iA) if (temAluno(st,i)) break;
		if (i==n) return;
		iA++;
		if (i == iA) iA++;
		assignStudent(st,i,iA,0);
	} else {
		if (!d) i = 1;
		else i = 0;
		for (;i<=iA&&l;i++) l = l->next;
		while (l&&!add) {
			sel = getData(l);
			if (canAddA(sel->uceName)) {
				insereAluno(st,sel->uceName);
				add = 1;
			}
			l = l->next;
		}
		if (!add) {
			arrayInsert(notAlloced,st);
		}
	}
}

static void tiraStudent (char *uce) {
	ArrayList *lst = arrayGet(allocNodes,getIndice(uce));
	int i,n=0;
	if (lst) {
		n = arrayGetLength(lst);
	}
	Student *st = arrayGet(lst,n-1);
	arrayRemoveFrom(lst,n-1);
	assignStudentA(st,uce,1);
}
static void insereAluno (Student *st, char *u) {
	ArrayList *tmp;
        int iA = getIndice(u);
        tmp = arrayGet(allocNodes,iA);
        if (!tmp) {
                tmp = newArrayList(STUDENT_LIST_SIZE);
                arrayInsertAt(allocNodes,iA,tmp,1);
        }
        arrayInsert(tmp,st);
	arraySort(tmp,studentCompareA,1);
}
static void insereLigacao (Student *st, char *uA, char *uB) {
	ArrayList *tmp;
	int iA = getIndice(uA);
	int iB = getIndice(uB);
	tmp = arrayGet(allocNodes,iA);
	if (!tmp) {
		tmp = newArrayList(STUDENT_LIST_SIZE);
		arrayInsertAt(allocNodes,iA,tmp,1);
	}
	arrayInsert(tmp,st);
	arraySort(tmp,studentCompareA,1);
	tmp = arrayGet(allocNodes,iB);
	if (!tmp) {
		tmp = newArrayList(STUDENT_LIST_SIZE);
		arrayInsertAt(allocNodes,iB,tmp,1);
	}
	arrayInsert(tmp,st);
	arraySort(tmp,studentCompareA,1);
	int c = getEdgeValue(allocGraph,iA,iB);
	setEdgeValue(allocGraph,iA,iB,c+1);
}

static void assignStudent (Student *st, int uce1, int uce2, int d) {
	char *uA, *uB, *uC;
	Selection *sel;
	LinkedList *lst;
	int i,s,iA,iB;
	uA = arrayGet(mapUCEs,uce1);
	uB = arrayGet(mapUCEs,uce2);
	iA = getIndiceLst(uA,st->selections);
	iB = getIndiceLst(uB,st->selections);
	s = listSize(st->selections);
	int c,b,aux,stop = 0;
	int add = 0;
	int v = 0;
	lst = st->selections;
	char *str;
	while (!add) {
		lst = st->selections;
		c = (iA > iB) ? iA : iB;
		b = (iA < iB) ? iA : iB;
		if (d) i=0;
		else i=1;
		for (;i<=c&&lst;i++) lst = lst->next;
		while (lst&&!add&&c<s-1) {
			str = arrayGet(mapUCEs,b);
			sel = getData(lst);
			if (canAdd(sel->uceName,str)) {
				insereLigacao(st,sel->uceName,str);
				add = 1;
			}
			lst = lst->next;
			c++;
		}
		iA++; iB++;
	}
	if (!add) {
		arrayInsert(notAlloced,st);
	}
}
static int canAddA (char *uce) {
        ChainingHashMap *map = getUCEsMap();
        UCE *aux; ArrayList *lst;
        int indA,indB,n;
        if (map) {
                aux = getChaining(map,uce);
                indA = getIndice(uce);
                lst = arrayGet(allocNodes,indA);
                n = arrayGetLength(lst);
                if (aux->maxStudents) if (n+1 > aux->maxStudents) return 0;
                return 1;
        }
        return 0;
}
static int canAdd (char *uceA, char *uceB) {
	ChainingHashMap *map = getUCEsMap();
	UCE *aux; ArrayList *lst;
	int indA,indB,n;
	if (map) {
		aux = getChaining(map,uceA);
		indA = getIndice(uceA);
		lst = arrayGet(allocNodes,indA);
		n = arrayGetLength(lst);
		if (aux->maxStudents) if (n+1 > aux->maxStudents) return 0;
		aux = getChaining(map,uceB);
		indB = getIndice(uceB);
		lst = arrayGet(allocNodes,indB);
		n = arrayGetLength(lst);
		if (aux->maxStudents) if (n+1 > aux->maxStudents) return 0;
		if (getEdgeValue(allocGraph,indA,indB) < 0) return 0;
		return 1;
	}
	return 0;
}
static int getIndiceLst (char *uce, LinkedList *ops) {
	int i = 0;
	LinkedList *lst = ops;
	Selection *sel;
	while (lst) {
		sel = getData(lst);
		if (!strcmp(sel->uceName,uce)) return i;
		i++;
		lst = lst->next;
	}
	return -1;
}

static void cortaLigacao (int uce1, int uce2) {
	ArrayList *uceA = arrayGet(allocNodes,uce1);
	ArrayList *uceB = arrayGet(allocNodes,uce2);
	Student *stA,*stB;
	int i,j,n,m,c;
	n = arrayGetLength(uceA);
	m = arrayGetLength(uceB);
	for (i=0;i<n;i++) {
		stA = arrayGet(uceA,i);
		for (j=0;j<m;j++) {
			stB = arrayGet(uceB,j);
			if (stA->number == stB->number) {
				arrayRemoveFrom(uceA,i);
				arrayRemoveFrom(uceB,j);
				assignStudent(stA,uce1,uce2,1);
				i--;
				break;
			}
		}
	}
	setEdgeValue(allocGraph,uce1,uce2,-1);
}

static int getIndice (char *uce) {
	int i = arrayIndexOf(mapUCEs,uce,equalityString);
	return i;
}

static void distribui () {
        ArrayList *students = getStudentsList();
        int i,n = arrayGetLength(students);
	Selection *sel1,*sel2;
        Student *st;
	ArrayList *tmp;
        int s1,s2,c,s = arrayGetLength(mapUCEs);
	allocGraph = newGraph(s);
	allocNodes = newArrayList(s);
	notAlloced = newArrayList(STUDENT_LIST_SIZE);
        for (i=0;i<n;i++) {
                st = arrayGet(students,i);
		if (st->type != EXTRA) {
                	sel1 = getData(st->selections);
			s1 = arrayIndexOf(mapUCEs,sel1->uceName,equalityString);
			if (s1 == -1) return; /* tem k ser diferente de -1! */
			tmp = arrayGet(allocNodes,s1);
			if (!tmp) {
				tmp = newArrayList(STUDENT_LIST_SIZE);
				arrayInsertAt(allocNodes,s1,tmp,1);
			}
			arrayInsert(tmp,st);
			if (st->ucesWanted > 1) {
				sel2 = getData(st->selections->next);
				s2 = arrayIndexOf(mapUCEs,sel1->uceName,equalityString);
				if (s2 == -1) return;
				tmp = arrayGet(allocNodes,s2);
                		if (!tmp) {
             		   	        tmp = newArrayList(STUDENT_LIST_SIZE);
             	   		        arrayInsertAt(allocNodes,s2,tmp,1);
             	  	 	}
               		 	arrayInsert(tmp,st);
				c = getEdgeValue(allocGraph,s1,s2);
				setEdgeValue(allocGraph,s1,s2,c+1);
			}
		}
	}
	for (i=0;i<s;i++) {
		tmp = arrayGet(allocNodes,i);
		if (tmp) arraySort(tmp,studentCompareA,1);
	}
}

static int compSelections (void *a, void *b) {
	Selection *a1 = a;
	Selection *b1 = b;
	if (a1->preference > b1->preference) return 1;
	else if (a1->preference < b1->preference) return (-1);
	else return 0;
}

static LinkedList * insereOmissoes (LinkedList *exist, ArrayList *all) {
	int i,n = arrayGetLength(all);
	Selection *sel;
	LinkedList *aux;
	int find = 0;
	LinkedList *new = NULL;
	for (i=0;i<n;i++) {
		aux = exist;
		while (aux&&!find) {
			sel = getData(aux);
			if (!strcmp(sel->uceName,arrayGet(all,i))) find = 1;
			aux = aux->next;
		}
		if (!find) new = insertElemHead(new,newSelection(arrayGet(all,i),0));
		else new = insertElemHead(new,sel);
	}
	freeLinkedList(exist);
	return new;
}

static int validaDados () {
	// É necessário validar os dados para ser possivel!
	ChainingHashMap *map;
	LinkedList *lst,*aux;
	ArrayList *stList;
	Selection *sel;
	int i,j,c = 0,n = 0;
	UCE *uce; Student *st;
	map = getUCEsMap(); // do project
	if (map) {
		mapUCEs = newArrayList(UCE_HASHMAP_SIZE);
		aux = lst = keySetChaining(map);
		while (aux) {
			arrayInsert(mapUCEs,getData(aux));
			aux = aux->next;
			c++;
		}
		if (c < 2) {
			printf("Tem que haver no minimo 2 UCEs\n");
			return 0;
		}
		freeLinkedList(lst);
		stList = getStudentsList();
		if (stList) n = arrayGetLength(stList);
		for (i=0;i<n;i++) {
			st = arrayGet(stList,i);
			aux = st->selections;
			while (aux) {
				sel = getData(aux);
				if (arrayIndexOf(mapUCEs,sel->uceName,equalityString) < 0) {
					printf("Aluno %d tem uma UCE não definida\n",st->number);
					return 0;
				}
				aux = aux->next;
			}
			st->selections = insereOmissoes(st->selections,mapUCEs);
			st->selections = sortList(st->selections,compSelections,0);
		}
	}
	return 1;
}

static void compoe (char *uce) {
	ChainingHashMap *map = getUCEsMap();
        UCE *aux; ArrayList *lst;
        int indA,indB,n;
        if (map) {
                aux = getChaining(map,uce);
                indA = getIndice(uce);
                lst = arrayGet(allocNodes,indA);
                n = arrayGetLength(lst);
		while (n > aux->maxStudents) {
			tiraStudent(uce);
			n--;
		}
        }
}

static void compoeAll () {
	int i,n = arrayGetLength(mapUCEs);
	for (i=0;i<n;i++) {
		compoe(arrayGet(mapUCEs,i));
        }
}
static Graph * clearGraph () {
	if (allocGraph == NULL) return NULL;
	Graph *g = newGraph(allocGraph->nodes);
	int i,j,c;
	for (i=0;i<g->nodes;i++) {
		for (j=0;j<g->nodes;j++) {
			c = getEdgeValue(allocGraph,i,j);
			if (c == -1) setEdgeValue(g,i,j,0);
			else setEdgeValue(g,i,j,c);
		}
	}
	return g;
}
static void assignExtra (Student *st) {
	Selection *sel,*sel1;
	int a,b;
	if (st->ucesWanted > 1) {
		sel = getData(st->selections);
		sel1 = getData(st->selections->next);
		a = arrayIndexOf(mapUCEs,sel->uceName,equalityString);
		b = arrayIndexOf(mapUCEs,sel1->uceName,equalityString);
		assignStudent(st,a,b,0);
	} else {
		sel = getData(st->selections);
		assignStudentA(st,sel->uceName,0);
	}
}
static void distribuiExtra () {
	ArrayList *students = getStudentsList();
	int n = arrayGetLength(students);
	int i; Student *st;
	for (i=0;i<n;i++) {
		st = arrayGet(students,i);
		if (st->type == EXTRA) {
			assignExtra(st);
		}
	}
}
static int probCount;
static int result = 0;
void executa () {
	probCount = 0;
	result = 0;
	if (!validaDados()) {
		printf("Existem dados em falta\n");
		return;
	}
	int cfg = 0;
	char *str = getConfigurationValue(CONFIG_HORARIOS);
	if (str) cfg = atoi(str);
	distribui();
	int max,n,s = allocGraph->nodes;
	int min,i,j,c;
	LinkedList *aux,*lst;
	Graph *g,*tmp,*m = NULL;
	int res[s],stop = 0,iA,iB;
	/*while (!stop) {
		probCount++;
		if (probCount > PROB_MAX) return; // TERMINOU!
		g = clearGraph();
		if (!g) return;
		aux = lst = getConnectedSubGraphs(g);
		m = getData(aux);
		max = colorGraph(m,res);
		aux = aux->next;
		while (aux) {
			tmp = getData(aux);
			n = colorGraph(tmp,res);
			if (n>max) max = n;
			aux = aux->next;
			if (n==max) m = tmp;
			else freeGraph(tmp);
		}
		freeLinkedList(lst);
		freeGraph(g);
		if (cfg) {
			if (max>cfg) {
				min = -1;
				for (i=0;i<m->nodes;i++) {
					for (j=0;j<m->nodes;j++) {
						c = getEdgeValue(m,i,j);
						if (i!=j) {
							if ((c && c < min) || c == -1) {
								iA = m->label[i];
								iB = m->label[j];
								min = c;
							}
						}
					}
				}
				if (min == -1) return ;
				cortaLigacao(iA,iB);
			} else stop = 1;
		} else stop = 1;
	}
	compoeAll();
	result = 1;
	distribuiExtra();*/
}

int hasResult () {
	return result;
}
static void validaResultDir () {
        int i,n = strlen(RESULT_DIR) + 4;
        char *path = (char *) malloc(sizeof(char)*n);
        sprintf(path,"%s",RESULT_DIR);
        FILE *fp;
	fp = fopen(path,"r");
        if (fp) fclose(fp);
        else mkdir(path,S_IRWXU | S_IRWXG | S_IRWXO);
        free(path);

}
static void validaResultProjectDir () {
	validaResultDir();
	char *name = getProjectName();
        int i,n = strlen(RESULT_DIR) + strlen(name) + 4;
        char *path = (char *) malloc(sizeof(char)*n);
        sprintf(path,"%s/%s",RESULT_DIR,name);
        FILE *fp;
        fp = fopen(path,"r");
        if (fp) fclose(fp);
        else mkdir(path,S_IRWXU | S_IRWXG | S_IRWXO);
        free(path);
}

static void criaDir (int i) {
	validaResultProjectDir();
	char *name = getProjectName();
        int n = strlen(RESULT_DIR) + strlen(name) + 20;
        char *path = (char *) malloc(sizeof(char)*n);
	sprintf(path,"%s/%s/%d",RESULT_DIR,name,i);
	mkdir(path,S_IRWXU | S_IRWXG | S_IRWXO);
	free(path);
}
static void writeInfo (Graph *tmp, int nColors, int colors[], int dir) {
	char *name = getProjectName();
	int i,n = strlen(RESULT_DIR) + strlen(name) + 20;
	char *path = (char *) malloc(sizeof(char)*n);
	sprintf(path,"%s/%s/%d/horarios",RESULT_DIR,name,dir);
	FILE *fp = fopen(path,"w");
	char *s;
	if (fp) {
		fprintf(fp,"Horários Necessários: %d (Variam de 1 a %d)\n",nColors,nColors);
		for (i=0;i<tmp->nodes;i++) {
			s = arrayGet(mapUCEs,tmp->label[i]);
			fprintf(fp,"%s (Horário %d)\n",s,colors[i]);
		}
		fclose(fp);
	}
	free(path);
}
static void writeStudentsA (Graph *tmp, int dir) {
	char *name = getProjectName();
        int i,j,n; Student *st;
	char *uce;ArrayList *lst;
	char *path; FILE *fp;
	for (i=0;i<tmp->nodes;i++) {
		uce = arrayGet(mapUCEs,tmp->label[i]);
		n = strlen(RESULT_DIR) + strlen(name) + 6 + strlen(uce);
		path = (char *) malloc(sizeof(char)*n);
        	sprintf(path,"%s/%s/%d/%s",RESULT_DIR,name,dir,uce);
        	lst = arrayGet(allocNodes,tmp->label[i]);
		fp = fopen(path,"w");
        	if (fp) {
			n = arrayGetLength(lst);
			for (j=0;j<n;j++) {
				st = arrayGet(lst,j);
				fprintf(fp,"%s (%d)\n",st->name,st->number);
			}
                	fclose(fp);
        	}
		free(path);
	}
}
CommandResult * command_executa (int argc, char *argv[]) {
	Graph *g;
	if (!hasProject()) {
		printf("É necessário ter um projecto carregado\n");
		return successCommandResult();
	}
	LinkedList *aux,*lst;
	Graph *tmp;
	int n,dir = 1;
	executa();
	g = clearGraph();
	if (!g) {
		printf("Sem UCE's para processar\n");
		return successCommandResult();
	}
	int res[g->nodes];
	if (hasResult()) {
		aux = lst = getConnectedSubGraphs(g);
		while (aux) {
			criaDir(dir);
			tmp = getData(aux);
			if (tmp) {
				criaDir(dir);
				n = colorGraph(tmp,res);
				writeInfo(tmp,n,res,dir);
				writeStudentsA(tmp,dir);
				freeGraph(tmp);
				dir++;
			}
			aux = aux->next;
		}
		freeLinkedList(lst);
		printf("Resultados calculados e escritos no devido local\n");
	} else printf("Não foi possivel calcular os horarios e alocações\n");
	return successCommandResult();
}
